//我们该如何理解递归，我们不要在意递归的展开图，把递归当成一个黑盒，然后关注进入和输出，我们赋予一个递归函数执念，然后
//相信递归可以自己完成，并且信任它，递归的出口为不能在进行分割的问题。
//我们应该如何写好一个递归？
//第一步先找到相同的子问题，这一步决定函数头是什么，第二步我们只关心这一个子问题如何解决，这一步决定函数体的书写,我们根据一个字问题，写出函数体，第三步为注意一个递归函数的出口是什么

// /合并两个有序的链表
//https://leetcode.cn/problems/merge-two-sorted-lists/?envType=study-plan-v2&envId=top-100-liked
//  * Definition for singly-linked list.
//  * struct ListNode {
//  *     int val;
//  *     ListNode *next;
//  *     ListNode() : val(0), next(nullptr) {}
//  *     ListNode(int x) : val(x), next(nullptr) {}
//  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
//  * };
//  */
// class Solution {
// public:
//     ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
//         // 我们赋予递归函数合并两个有序数组的任务，然后相信它一定能完成
//         if (list2 == nullptr) {
//             return list1;
//         }
//         if (list1 == nullptr) {
//             return list2;
//         }
//         if (list1->val > list2->val) {
//             list2->next = mergeTwoLists(list1, list2->next);
//             return list2;
//         }
//         else
//         {
//             list1->next= mergeTwoLists(list1->next, list2);
//             return list1;
//         }
//     }
// 
//递归 VS 深度优先遍历 递归的展开图其实就是对树做一个深度优先遍历
//循环 VS 递归 可以相互转化

//反转链表
//https://leetcode.cn/problems/reverse-linked-list/?envType=study-plan-v2&envId=top-100-liked
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
// class Solution {
// public:
//     ListNode* reverseList(ListNode* head) {
//         //这是递归的作用，把当前节点的后面逆序，然后返回头节点，然后把当前节点添加进去
//         if(!head || !head->next)
//         {
//             return head;
//         }
//         ListNode* node = reverseList(head->next);
//         head->next->next = head;
//         head->next = nullptr;
//         return node;    
//     }
// };


//两两交换链表中的节点
//https://leetcode.cn/problems/swap-nodes-in-pairs/?envType=study-plan-v2&envId=top-100-liked
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
// class Solution {
// public:
//     ListNode* swapPairs(ListNode* head) 
//     {
    
//     return dfs(head);
        
//     }
//     ListNode* dfs(ListNode* first)
//     {
//         //我们需要先交换两个节点
//         if (first == nullptr || first->next == nullptr) {
//             return first;
//         }
//         ListNode* second = first->next;
//         ListNode* next = second->next;
//         second->next = first;
//         first->next = dfs(next);
//         return second;
//     }

//     //我们递归函数要做的是交换两个节点，然后返回一个节点供上层相连接
// };

// https://leetcode.cn/problems/powx-n/
// class Solution {
// public:
//     double myPow(double x, int n) {
//         if(n < 0)
//         {
            
//              return 1/Pow(x,-(long long)n);
//         }
//       return Pow(x,n);
//     }
//     double Pow(double x , long long n)
//     {
//          // 我们这个函数的作用是返回x的n次幂
//         if (n == 0) {
//             return 1;
//         }
//         double ret = Pow(x, n / 2);
//         return n % 2 == 1 ? ret * ret * x : ret * ret;
//     }
// };



// https://leetcode.cn/problems/validate-binary-search-tree/?envType=study-plan-v2&envId=top-100-liked
// /**
//  * Definition for a binary tree node.
//  * struct TreeNode {
//  *     int val;
//  *     TreeNode *left;
//  *     TreeNode *right;
//  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
//  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
//  * right(right) {}
//  * };
//  */
// class Solution {
// public:
//     long prev = LONG_MIN; // 前驱节点
//     bool isValidBST(TreeNode* root) {
//         // 我们的递归函数判断的是左右两边的树是不是二叉搜索树
//         return dfs(root);
//     }
//     bool dfs(TreeNode* root) {
//         if(!root)
//         {
//             return true;
//         }
//         bool left = dfs(root->left);
//         bool cur = false;
//         if (root->val > prev) {
//             prev = root->val;
//             cur = true;
//         } else {
//             cur = false;
//         }
//         bool right = dfs(root->right);
//         return right && left && cur;
//     }
// };

